package cn.edu.xjtu.work.relativeSortArray;

/**
 * 1122. 数组的相对排序
 * 
 * 给你两个数组，arr1 和 arr2，
 * 
 * arr2 中的元素各不相同 arr2 中的每个元素都出现在 arr1 中 对 arr1 中的元素进行排序，使 arr1
 * 中项的相对顺序和 arr2 中的相对顺序相同。未在 arr2 中出现过的元素需要按照升序放在 arr1 的末尾。
 * 
 * 来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/relative-sort-array
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class Solution {

    /**
     * 计数排序
     * 
     * @param arr1
     * @param arr2
     * @return
     */
    public int[] relativeSortArray(int[] arr1, int[] arr2) {
        int max = 0;
        for (int i = 0; i < arr1.length; i++) {
            max = Math.max(max, arr1[i]);
        }

        int[] list = new int[max + 1];
        for (int i : arr1) {
            list[i]++;
        }
        int[] ret = new int[arr1.length];
        int index = 0;
        for (int i : arr2) {
            while (list[i] != 0) {
                ret[index++] = i;
                list[i]--;
            }
        }
        for (int i = 0; i < list.length; i++) {
            while (list[i] != 0) {
                ret[index++] = i;
                list[i]--;
            }
        }
        return ret;

    }
}
